package ercahshu

func preorderTraversal(root *TreeNode) []int {
	if root == nil {
		return make([]int, 0)
	}
	ans := make([]int, 0)
	var df func(node *TreeNode)
	df = func(node *TreeNode) {
		ans = append(ans, node.Val)
		df(node.Left)
		df(node.Right)
	}
	df(root)
	return ans
}

// 所谓的前中后序遍历都是指的中间节点的位置

// 迭代解法

func preorderTraversal1(root *TreeNode) []int {
	ans := make([]int, 0)
	stack := make([]*TreeNode, 0)
	node := root
	for node != nil || len(stack) > 0 {
		for node != nil {
			stack = append(stack, node)
			ans = append(ans, node.Val)
			node = node.Left
		}
		node = stack[len(stack)-1].Right
		stack = stack[:len(stack)-1]
	}
	return ans
}
